Masala #0453

Isfandiyor Liplandiya davlatiga asos soldi. Liplandiya $n$ ta shahar va ular orasida $n-1$ ta yo’l bor (Liplandiyani daraxt – oddiy, bog’lamli va sikllarsiz graf deyishimiz mumkin).

Isfandiyor Liplandiyaning poytaxtini $1$ – shahar deb nomladi. So’ngra u $1$-shahardan eng yaqin hali raqamlanmagan (agar eng yaqinlari bir nechta bo’lsa ixtiyoriysiga bordi) shaharga bordi va o’sha shaharni $2$-shahar deb nomladi. So’ngra $2$-shaharga eng yaqin hali raqamlanmagan shaharga borib uni $3$-shahar deb nomladi. Shu tartibda shaharlarga $1...n$ sonlar bilan raqamlab chiqdi.

$dist(a,b)$ deb $a$ shahardan $b$ shaharga boruvchi eng qisqa yo’lning uzunligini ataymiz. Sizga $q$ ta so’rovda $x$ soni beriladi. Sizning vazifangiz $dist(a,b) \geq x$ bo’lgan leksikografik eng kichik $(a,b)$ juftlikni topish.

Birinchi qatorda $n$ natural son $(2 \leq n \leq 200000)$.
Keyingi $n-1$ ta qatorda 𝑎 va 𝑏 qo’shni shaharlar raqamlari beriladi $(1 \leq a, b \leq n, a \neq b)$.
Keyingi qatorda $q$ natural son $(1 \leq q \leq 200000)$.
Keyingi $q$ ta qatorda $x$ butun son $(0 \leq x < n)$.

Kiritilgan graf daraxt ekanligi va shaharlar Isfandiyor xohlaganiday raqamlangani kafolatlanadi.

Har bir so’rov uchun agarda bunday juftlik mavjud bo’lsa, leksikografik eng kichigini, aks holda ikkita $-1$ ni chop eting.